package BinarysearchTree;

import java.sql.ClientInfoStatus;
import java.util.ArrayList;
import java.util.List;

public class BinaryTree implements BinarySearchTreeInterface{

    BinaryNode root = null;
    static class BinaryNode {
        int key;
        Object value;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(int ket, Object value) {
            this.key = ket;
            this.value = value;
        }

        public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    @Override
    public Object get(int key) {
        return getRecursion(root,key);
    }
    //使用递归实现
    private Object getRecursion(BinaryNode node, int key) {
        if (node == null) {
            return null;
        }
        if (node.key < key) {
            return getRecursion(node.right,key);
        }else if (node.key > key) {
            return getRecursion(node.left,key);
        }else {
            return node.value;
        }
    }

    //使用非递归实现
    public Object getNotRecursion(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while (p != null) {
            if (p.key < key) {
                p = p.right;
            } else if (p.key > key) {
                p = p.left;
            }else {
                return p.value;
            }
        }
        return null;
    }

    @Override
    public Object min() {
        return minRecursion(root);
    }
    //使用递归实现
    private Object minRecursion(BinaryNode node) {
        if (node == null) {
            return  null;
        }
        if (node.left == null) {
            return node.value;
        }
        return minRecursion(node.left);
    }

    //使用非递归实现
    public Object minNotRecursion(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    @Override
    public Object max() {
        return maxRecursion(root);
    }
    //使用递归实现
    private Object maxRecursion(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return maxRecursion(node.right);
    }

    //使用非递归实现
    public Object maxNotRecursion(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    @Override
    public void put(int key, Object value) {
        BinaryNode parents = null;
        //先来试找 key 关键字
        BinaryNode p = root;
        while (p != null) {
            parents = p;
            if (p.key < key) {
                p = p.right;
            }else if (p.key > key) {
                p = p.left;
            }else {
                break;
            }
        }
        if (p != null) {
            //说明有 key 这个关键字了，直接更新值即可
            p.value = value;
            return;
        }

        //说明 root == null
        if (parents == null) {
            root = new BinaryNode(key,value);
            return;
        }

        //说明没有 key 这个关键字，需要创建一个 key 的节点
        if ( key < parents.key) {
            parents.left = new BinaryNode(key,value);
        } else {
            parents.right = new BinaryNode(key, value);
        }
    }

    //分两种情况:
    //第一种，当前节点有左子树时，该前驱则为左子树的最大关键字key
    //第二种，当前节点没有左子树，那么该前驱则为从自左向右来的祖宗
    @Override
    public Object predecessor(int key) {
        if (root == null) {
            return null;
        }
        //找来找 key 关键字
        BinaryNode successorLeft = null;
        BinaryNode p = root;
        while (p != null) {
            if (p.key < key ){
                successorLeft = p;
                p = p.right;
            }else if (p.key > key) {
                p = p.left;
            }else {
                break;
            }
        }
        //不存在该节点，则返回null
        if (p == null) {
            return null;
        }
        //第一种情况:
        if (p.left != null) {
            return maxRecursion(p.left);
        }
        //当该节点没有前驱，则返回null
        if (successorLeft == null) {
            return null;
        }
        //第二种情况:
        return successorLeft.value;
    }


    //分为两种情况:
    //第一种，当前节点有右子树，则该后驱为右子树的最小key
    //第二种，当前节点没有右子树，则该后驱为从右先左来的祖宗
    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode predecessorRight = null;
        BinaryNode p = root;
        while (p != null) {
            if (p.key < key) {
                p = p.right;
            }else if (p.key > key) {
                predecessorRight = p;
                p = p.left;
            }else {
                break;
            }
        }
        //没有找到该关键字
        if (p == null) {
            return null;
        }
        //第一种情况
        if (p.right != null) {
            return minNotRecursion(p.right);
        }

        //没有找到前驱
        if (predecessorRight == null) {
            return null;
        }
        //第二种情况
        return predecessorRight.value;
    }

    //分为四种情况考虑
    //第一种情况:删除的节点只有左孩子
    //第二种情况:删除的节点只有右孩子
    //第三种情况:删除的节点没有左右孩子
    //第四种情况:删除的节点有左右孩子
    @Override
    public Object delete(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode parent = null;
        BinaryNode p = root;
        while (p != null) {

            if (p.key < key) {
                parent = p;
                p = p.right;
            } else if (p.key > key) {
                parent = p;
                p = p.left;
            }else {
                break;
            }
        }
        //没找到相对应的节点key
        if (p == null) {
            return null;
        }
        //第一、二、三种情况
        if (p.right == null ) {
            shift(parent,p,p.left);
        } else if (p.left == null) {
            shift(parent,p,p.right);
        }else {
            //第四种情况
            BinaryNode successor = p.right;
            BinaryNode successorParent = p;
            while (successor.left != null) {
                successorParent = successor;
                successor = successor.left;
            }
            //说明不是紧邻关系，需要对 successor 的后序进行处理
            if (successorParent != p) {
                shift(successorParent,successor,successor.right);
                successor.right = p.right;
            }

            shift(parent,p,successor);
            successor.left = p.left;

        }
        return p.value;
    }
    private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
        if (parent == null) {
            root = next;
        } else if (parent.left == delete) {
            parent.left = next;
        } else  {
            parent.right = next;
        }
    }

    //使用递归实现
    private final List<Object> list = new ArrayList<>();
    public  Object deleteRecursion(int key) {

        root = deRecursion(root,key);
        return list.get(0);
    }
    private BinaryNode deRecursion(BinaryNode node, int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
           node.left = deRecursion(node.left,key);
           return node;
        }else if (node.key < key) {
            node.right = deRecursion(node.right,key);
            return node;
        }
        list.add(node.value);
        //找到该节点了
        //第一种情况: 只有左孩子或者均为空
        if (node.right == null) {
            return node.left;
        } else if (node.left == null) {
            return node.right;
        }
        //第三种情况: 存在左右孩子
        BinaryNode p = node.right;
        while (p.left != null) {
            p = p.left;
        }
        //先处理该节点的孩子节点
        BinaryNode nodeRight = node.right;
        p.right = deRecursion(nodeRight, p.key);
        p.left = node.left;
        return p;
    }

}
